package leetcode.dp;

import java.util.stream.IntStream;

public class MinimumFallingPathSum931 {
    class Solution1 {
        public int minFallingPathSum(int[][] matrix) {
            if (matrix == null || matrix.length == 0|| matrix[0] == null || matrix[0].length == 0) {
                return 0;
            }
            int n = matrix.length;
            int[][] dp = new int[n][n];
            dp[0] = matrix[0];
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j != 0 && j != n - 1) {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1]), dp[i - 1][j]) + matrix[i][j];
                    } else if (j == 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                    } else if (j == n - 1) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
                    }
                }
            }
            return IntStream.of(dp[n - 1]).min().getAsInt();
        }
    }

    class Solution2 {
        public int minFallingPathSum(int[][] matrix) {
            if (matrix == null || matrix.length == 0|| matrix[0] == null || matrix[0].length == 0) {
                return 0;
            }
            int n = matrix.length;
            int[][] dp = new int[2][n];
            dp[0] = matrix[0];
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j != 0 && j != n - 1) {
                        dp[i & 1][j] = Math.min(Math.min(dp[(i - 1) & 1][j - 1], dp[(i - 1) & 1][j + 1]), dp[(i - 1) & 1][j]) + matrix[i][j];
                    } else if (j == 0) {
                        dp[i & 1][j] = Math.min(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j + 1]) + matrix[i][j];
                    } else if (j == n - 1) {
                        dp[i & 1][j] = Math.min(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - 1]) + matrix[i][j];
                    }
                }
            }
            return IntStream.of(dp[(n - 1) & 1]).min().getAsInt();
        }
    }
}
